package other;

import java.security.PublicKey;
import java.util.*;
import java.util.stream.Collector;
import java.util.stream.Collectors;

import junit.*;

public class Ex139 {
    static class Solution {
    
        //使用f[i]表示前i位是否可以用字典的字符串表示
        public boolean wordBreak2(String s, List<String> wordDict) {
            int len = s.length();
            boolean[] f = new boolean[len + 1];
            f[0] = true; //空串的情况设置为true，使得第一个字符的判断没有问题

            next: for (int i = 1; i <= len; i++) {
                loop: for (int j = 0; j < wordDict.size(); j++) {
                    String str = wordDict.get(j);
                    int l = str.length();
                    if (str.charAt(l - 1) == s.charAt(i - 1)) {
                        //若扣去当前子字符串导致下标<0或者上一个位置不成立，这个字符串被淘汰
                        if (i - l < 0 || !f[i - l]) continue;
                        else {
                            //开始检测这个字符串是否匹配
                            int idx = 0;
                            while (idx < l) {
                                if (str.charAt(idx) != s.charAt(i - l + idx)) continue loop;
                                idx++;
                            }
                            if (idx == l) {
                                f[i] = true;
                                continue next;
                            }
                        }
                    }
                }
            }
            return f[len];
        }


        //记忆化的dfs
        Map<Character, List<String>> map;
        String s;
        int[] p;
        public boolean wordBreak1(String s, List<String> wordDict) {
            map = new HashMap<>();
            for (String str: wordDict) {
                char c = str.charAt(0);
                if (map.containsKey(c)) {
                    map.get(c).add(str);
                } else {
                    List<String> dic = new ArrayList<>(){{add(str);}};
                    map.put(c, dic);
                }
            }
            p = new int[s.length()];
            System.out.println(map);
            this.map = map;
            this.s = s;
            return dfs(0);
        }

        public boolean dfs(int idx) {
            if (idx == s.length()) return true;
            int k = 0;
            boolean res = false;
            List<String> dic = map.get(s.charAt(idx));
            if (dic == null) {
                System.out.println(s + "-------------" + idx);
                return false;
            }
            loop: for (int i = 0; i < dic.size(); i++) {
                String str = dic.get(i);
                int j = 0;
                for (; j < str.length() && idx + j < s.length(); j++) {
                    if (s.charAt(idx + j) != str.charAt(j)) continue loop;
                }
                // if (idx + j == s.length()) return true;
                if (j == str.length()) {
                    if (idx + j < p.length && p[idx + j] == 0) {
                        p[idx + j] = dfs(idx + j) ? 1 : -1;
                    }
                    
                    if (idx + j >= p.length) {
                        res = true;
                    } else {
                        res = res || (p[idx + j] > 0);
                    }
                    if (res) return true;
                }
            }
            return res;
        }

        public boolean wordBreak(String s, List<String> wordDict) {
            int len = s.length();
            boolean[] f = new boolean[len + 1];
            f[0] = true;
            for (int i = 1; i <= len; i++) {
                String str = s.substring(0, i);
                for (int j = 0; j < wordDict.size(); j++) {
                    String t = wordDict.get(j);
                    if(str.equals(t)) {
                        int l = t.length();
                        if (i - l >= 0 && f[i - l]) {
                            f[i] = true;
                            break;
                        }
                    }
                }
            }
            return f[len];
        }
    }


    /* 
    
    String t = wordDict.get(j);
                     if(str.equals(t)) {
                         int l = t.length();
                         if (i - l >= 0 && f[i - l]) {
                             f[i] = true;
                             last = i;
                             break;
                         }
                     }
    
    */
   static class Solution2 {
        public boolean wordBreak(String s, List<String> wordDict) {
             int len = s.length();
             boolean[] f = new boolean[len + 1];
             f[0] = true;
             int last = 0;
             Set<String> dic = wordDict.stream().collect(Collectors.toSet());
             for (int i = 1; i <= len; i++) {
                
                 for (int j = i - 1; j >= 0; j--) {
                    String str = s.substring(j, i);
                    if (dic.contains(str)) {
                         int l = str.length();
                         if (i - l >= 0 && f[i - l]) {
                             f[i] = true;
                             last = i;
                             break;
                         }
                
                    }
                    System.out.println(str);
                 }
             }
             System.out.println(Arrays.toString(f));
             return f[len];
         }
 }

 static class Solution3 {
     //BFS解法，只入队有参考价值的节点
    public boolean wordBreak(String s, List<String> wordDict) {
         int len = s.length();
         boolean[] visited = new boolean[len];
         Queue<Integer> queue = new LinkedList<>();
         Set<String> dic = wordDict.stream().collect(Collectors.toSet());

         //从第一个字符开始考虑
         queue.offer(0);
         while (!queue.isEmpty()) {
             int start = queue.poll();
             if (visited[start]) continue;
             for (int i = start + 1; i <= len; i++) {
                 String str = s.substring(start, i);
                if (dic.contains(str)) {
                    queue.offer(i);
                    if (i == len) return true;
                }
             }
             visited[start] = true;
         }
         return false;
     }
}
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        String s = "applepenapple";
        s = "leetcode";
        List<String> list = new ArrayList<>(){{
            // add("apple");
            // add("pen");
            add("leet");
            add("code");
        }};
        System.out.println(solution.wordBreak(s, list));   
    }
}







/*
     public boolean dfs(int i) {
            if (i >= len) return true;
            List<String> dic = map.get(s.charAt(i));
            boolean res = false;
            for (int j = 0; j < dic.size(); j++) {
                String str = dic.get(j);
                int idx = 0;
                while (idx < str.length()) {
                    if (s.charAt(i + idx) != str.charAt(idx)) continue;
                }
                return dfs()
            }

            return res;
        }

*/